package cn.zyl.demo.java.sort;

/**
 * SelectionSort 类说明: 选择排序
 * <p> 选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。 </p>
 * <p> 用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧 </p>
 *
 * @author wsz
 * @version v1.0
 * @date 2020-08-13
 */
public class SelectionSort extends AbstractArraySortSimple{
    /**
     * 排序接口
     * <p>算法步骤</p>
     * <p>1.首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置</p>
     * <p>2.再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾</p>
     * <p>3.重复第二步，直到所有元素均排序完毕</p>
     * @param sourceArray 待排序数组
     * @param order       排序方式，(默认)升序 true；降序 false
     * @return 排序后的数组
     * @throws Exception 异常信息
     */
    @Override
    public Integer[] sort(Integer[] sourceArray, Boolean order) throws Exception {
        Integer[] arr = copyArray(sourceArray);
        //极限值，升序 最小值下标；降序 最大值下标
        int limitIndex;
        start();
        //总共要经过 N-1 轮比较
        for (int i = N_0,len = arr.length ; i < len ; i++) {
            limitIndex = i;
            //每轮需要比较的次数N-i
            for (int j = i+N_1; j < len; j++) {
                if(order){
                    //记录目前能找到的最小值下标
                    if(arr[j] < arr[limitIndex]){ limitIndex = j; }
                }else {
                    //记录目前能找到的最大值下标
                    if(arr[j] > arr[limitIndex]){ limitIndex = j; }
                }
            }
            //将找到的最小/大值和i位置所在的值进行交换
            if(i != limitIndex){
                addOne();
                swapValBit(arr, i, limitIndex);
            }
        }
        end();
        return arr;
    }

    public static void main(String[] args) {
        int len =15,max=100;
        //待排序数组初始化
        Integer[] arr = randomArray(len,max);
        AbstractArraySortSimple sort = new SelectionSort();
        try {
            System.out.println("升序操作");
            printArray(sort.sort(arr, true));
            System.out.println("降序降序");
            printArray(sort.sort(arr, false));
        }catch (Exception e){
            e.printStackTrace();
        }
    }
}
